public class HashMapDemo<K, V> implements Map<K, V> {
    //table的length是2的n次方
    private EntryDemo<K, V>[] table = new EntryDemo[16];
    //已经保存的有效key的个数
    private int size = 0;

    private static final double LOAD_FACTOR_THRESHOLD = 0.75;

    @Override
    public V get(K key) {
        //1.根据key得到下标
        //1.1求出key的hashCode();
        //这里使用了hashCode(),如果使用自定义的类作为HashMap的K类型，
        // 则必须在类中覆写hashCode()方法，否则无法根据相同的key找到唯一的下标
        int hash = key.hashCode();
        hash = (hash >> 16) ^ hash;//让hash中的每一位都参与到运算当中，使得找到的下标尽可能均匀。

        //1.2利用hash得到合法的下标
        int index = hash & (table.length - 1);//这里就用到了table的length为2的幂次方这一特点

        //2.使用下标找到链表的头节点的引用
        EntryDemo<K, V> head = table[index];

        //3.在链表中，找到包含key的结点，返回存在结点中的value，即和key关联的value
        //遍历链表去找
        EntryDemo<K, V> node = head;
        while (node != null) {
            if (key.equals(node.key)) {//如果使用自定义类作为HashMap的key，必须覆写equals
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    @Override
    public V put(K key, V value) {

        int hash = key.hashCode();
        hash = (hash >>> 16) ^ hash;

        //1.2利用hash得到合法的下标
        int index = hash & (table.length - 1);

        //2.使用下标找到链表的头节点的引用
        EntryDemo<K, V> head = table[index];

        //3.在链表中，找到包含key的结点，返回存在结点中的value，即和key关联的value
        //遍历链表去找
        EntryDemo<K, V> node = head;
        while (node != null) {
            if (key==null&&node.key==null){
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            else if (key.equals(node.key)) {//找到的情况
                //使用新的value，替换原来的value，并返回原来的value
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            node = node.next;
        }
        //没找到的情况，使用key-value新建结点，并把结点插入到链表中
        EntryDemo<K, V> entryDemo = new EntryDemo<>(key, value);
        //插入：头插or尾插
        //如果不考虑多线程，头插比较简单，如果考虑多线程，头插可能产生一些问题，所以1.8之后使用尾插
        //我们选择使用尾插
        if (head == null) {//一个结点都没有的情况下
            table[index] = entryDemo;
        } else {
            EntryDemo<K, V> last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = entryDemo;
        }
        size++;
        //为了减少冲突率，通过调节负载因子size/table.length的值
        //设定一个阈值，当size/table.length大于某个值时，进行扩容
        //所谓的扩容就是保持size不变，让table.length变大，进而使得size/table.length降低，进而减少冲突率
        if (size * 1.0 / table.length > LOAD_FACTOR_THRESHOLD) {
            resize();
        }

        return null;
    }

    //所谓的扩容，需要

    /**
     * 1.保证table.length依然是2的幂次方
     * 2.因为table.length变化了，所以key对象的下标一定会变化，所以需要把所有的key重新计算下标，重新插入
     */
    private void resize() {
        //保证长度为2的幂次方
        EntryDemo<K, V>[] newTable = new EntryDemo[table.length * 2];

        //遍历原来的所有链表(数组)
        for (int i = 0; i < table.length; i++) {
            EntryDemo<K, V> head = table[i];
            //head是一条条链表的头节点的引用
            //遍历链表中的每一个结点，把key-value重新插入到newTable中
            EntryDemo<K, V> node = head;
            while (node != null) {
                K key = node.key;
                V value = node.value;

                //利用key求新的下标
                int hash = key.hashCode();
                hash = (hash >>> 16) ^ hash;
                int index = hash & (newTable.length - 1);

                //在新的数组的链表中遍历
                EntryDemo<K, V> newHead = newTable[index];
                //选择头插
                EntryDemo<K, V> entry = new EntryDemo<>(key, value);
                entry.next = newTable[index];
                newTable[index] = entry;

                node = node.next;
            }
        }
        //原来的table不要了，使用newTable替换掉原来的table
        table = newTable;
    }
}
